package main

import "fmt"

func main() {
	arr := []int{4, 2, 22, 4, 5, 456, 2, 45, 45, 3, 34, 523, 5, 4, 0, 3, 1}
	fmt.Println(quickSort(arr))
}

func Swap(arr []int, i, j int) []int {
	temp := arr[i]
	arr[i] = arr[j]
	arr[j] = temp
	return arr
}

/*
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
*/

func quickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	middle := arr[0]
	var left []int
	var right []int
	for i := 1; i < len(arr); i++ {
		if arr[i] > middle {
			right = append(right, arr[i])
		} else {
			left = append(left, arr[i])
		}
	}
	middle_s := []int{middle}
	left = quickSort(left)
	right = quickSort(right)
	arr = append(append(left, middle_s...), right...)
	return arr
}
